package s6_排序算法.sort3_插入排序;

import s6_排序算法.BaseSort;

import java.util.Arrays;

/**
 * @author wisdomelon
 * @date 2020/7/28 0028
 * @project data_study
 * @jdk 1.8
 * 插入排序
 */
public class InsertionSort extends BaseSort {

    public static void main(String[] args) {
        int arr[] = simple();
        System.out.println(Arrays.toString(arr));
        new InsertionSort().asc(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Override
    public void asc(int[] arr) {

        System.out.println("InsertionSort-------------------------------");
        long s = System.currentTimeMillis();

        method1(arr);

        //method2(arr);

        long e = System.currentTimeMillis();
        System.out.println("InsertionSort: " + (e-s) + "ms");

    }

    private void method2(int[] arr) {
        // 遍历数组，从第二个元素开始遍历，第一个元素没有比较的前置元素，因此无需遍历
        for(int i=1; i<arr.length; i++) {

            int res = arr[i];
            int index = i-1;

            // 前一位索引下的值不小于0 且 记录的元素值 比 前一位索引下的值要小， 说明记录的值是小值
            while(index >= 0 && res < arr[index]) {
                // 将前一位索引的值 放到 当前索引下  相当于元素值后移一位
                arr[index + 1] = arr[index];
                // 索引减少
                index--;
            }
            if(index + 1 != i) {
                arr[index + 1] = res;
            }
        }
    }

    private void method1(int[] arr) {
        // 遍历数组，从第二个元素开始遍历，第一个元素没有比较的前置元素，因此无需遍历
        for(int i=1; i<arr.length; i++) {
            int res = arr[i];
            // 从数组第二个元素开始，记录当前元素的值，依次与前一个元素比较，如果比前一个小，则交换位置，如果比前一个元素大，则终止比较
            for(int j = i; j > 0; j--) {
                if(arr[j-1] < res) {
                    break;
                }
                arr[j] = arr[j-1];
                arr[j-1] = res;
            }
        }
    }
}
